#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
#include<vector>
#include<algorithm>
#include<math.h>
using namespace std;


//class Solution {
//public:
//    vector<int> searchRange(const vector<int>& nums, int target) {
//        int n = nums.size();
//        if (n == 0) return { -1,-1 };
//        int left = 0, right = n - 1;
//        while (left < right)
//        {
//            int mid = (left + right) / 2;
//            if (nums[mid] < target)
//            {
//                left = mid + 1;
//            }
//            else right = mid;
//        }
//        int begin = left;
//        if (nums[begin] != target)
//            return { -1,-1 };
//        left = 0, right = n - 1;
//        while (left < right)
//        {
//            int mid = (left + right + 1) / 2;
//            if (nums[mid] <= target)
//            {
//                left = mid;
//            }
//            else right = mid - 1;
//        }
//        int end = right;
//
//        return { begin,end };
//
//    }
//};
//
//
//int main()
//{
//    Solution st;
//    vector<int> ret = st.searchRange({ 5,7,7,8,8,10 }, 8);
//    for (auto& x : ret)
//    {
//        cout << x << " ";
//    }
//    return 0;
//}




//typedef long long int LL;
//const int N = 1e5 + 10;
//
//LL n, a[N], q, x, y, Begin, End;
//int main()
//{
//    cin >> n;
//    for (int i = 0; i < n; i++)
//    {
//        cin >> a[i];
//    }
//    cin >> q;
//    for (int i = 0; i < q; i++)
//    {
//        cin >> x >> y;
//        int left = 0, right = n - 1;
//        while (left < right)
//        {
//            LL mid = (left + right) / 2;
//            if (a[mid] < x)
//                left = mid + 1;
//            else
//                right = mid;
//        }
//        if (a[left] >= x)
//            Begin = left;
//        else
//        {
//            cout << "0" << endl;
//            continue;
//        }
//        left = 0; right = n - 1;
//        while (left < right)
//        {
//            LL mid = (left + right + 1) / 2;
//            if (a[mid] > y)
//                right = mid - 1;
//            else
//                left = mid;
//        }
//        if (a[right] <= y)
//            End = right;
//        else
//        {
//            cout << "0" << endl;
//            continue;
//        }
//        cout << End - Begin + 1 << endl;
//    }
//
//    return 0;
//}

//typedef long long int LL;
//
//const int N = 2e5 + 10;
//LL a[N], n, C, Begin = -1, End = -1;
//
//
//int main()
//{
//	int count = 0;
//	cin >> n >> C;
//	for (int i = 1; i <= n; i++)
//	{
//		cin >> a[i];
//	}
//
//	sort(a + 1, a + n + 1);
//	for (int j = 2; j <= n; j++)
//	{
//		int A = a[j];
//		int B = A - C;
//		int left = 1, right = j - 1;
//		while (left < right)
//		{
//			int mid = (left + right + 1) / 2;
//			if (a[mid] <= B)
//				left = mid;
//			else right = mid - 1;
//		}
//		if (a[right] == B)
//			End = right;
//		left = 0, right = j - 1;
//		while (left < right)
//		{
//			int mid = (left + right) / 2;
//			if (a[mid] < B)
//			{
//				left = mid + 1;
//			}
//			else right = mid;
//		}
//		if (a[left] == B)
//			Begin = left;
//		if (Begin == -1 || End == -1)
//			continue;
//
//		count += End - Begin + 1;
//	}
//
//	cout << count;
//
//
//	return 0;
//}
